package com.rui.study.algorithm.P_单链表环的检测;

/**
 * @program: study_20180903
 * @description: 链表中环的检测
 * @author: Yaowr
 * @create: 2018-10-22 09:43
 **/


import com.rui.study.algorithm.ListNode;

import java.util.HashSet;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        ListNode p = head;
        while(p != null) {
            if (!set.add(p)) {
                break;
            }
            p = p.next;
        }
        return p;
    }

    public static void main(String[] args) {

        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node1;


        Solution solution = new Solution();
        ListNode r = solution.detectCycle(node1);
        if (r != null) {

            System.out.println(r.val);
        } else {
            System.out.println(r);
        }
    }

    public static String print(ListNode head) {
        if (head == null) {
            return "";
        }
        String nextVal = print(head.next);
        if (nextVal.length() > 0) {
            nextVal = "->" + nextVal;
        }
        return head.val + nextVal;
    }
}